#include <iostream>
#include <vector>
using namespace std;
long long sum = 0;
vector<int> dp;
int fun(int n) {
    sum++;
    if (n < 3) return n;
    if (dp[n] != -1) return dp[n];
    dp[n] = 1;
    return fun(n - 1) + fun(n - 2);
}
void get(int n) {
    sum = 0;
    fun(n);
    cout << "n= " << n << "sum=" << sum << "\n";
}
int main() {
    dp.resize(20000, -1);
    get(5000);
    get(8000);
    get(10000);
}
